\section{Approach}
\label{subsec:approach}

In this section, we will describe our approach in using a variant of AspectJ
, Aspect Benchmark Compiler (Section~\ref{subsec:abc}),
to detect and resolve two problems that we want to address: Deadlock
(Section~\ref{subsec:deadlock_abc}) and Infinite Loop
(Section~\ref{subsec:infinite_loop_abc}).

\subsection{Aspect Benchmark Compiler}
\label{subsec:abc}
AspectJ is a tool that makes use of aspect oriented technique to extend Java in
resolving cross-cutting concerns that can make development elegant and less
error prone. It's kernel is using the ajc compiler.

However, AspectJ is lacking several features such as detecting deadlock and
infinite loop. We would want to extend the capabilities of AspectJ to perform
such functions. We explored AspectJ and found that its extensibility feature is
limited and thus could not enable us to perform our tasks in detecting deadlock
and locating infinite loops easily.
Therefore, we have chosen a variant of AspectJ, Aspect Benchmark Compiler (abc) that works
exactly as AspectJ and is able to perform more aggressive optimisations and is
easily extensible. In figure~\ref{fig:abc}, we can see that all AspectJ's
features are being implemented in ABC, and ABC can further extended to provide
more features using aspects in Java.

\begin{figure}
    \centering
    \includegraphics{images/abc.png}
    \caption{The structual semantics of Aspect Benchmark Compiler.}
    \label{fig:abc}
\end{figure}

\subsection{Detecting Deadlock using ABC}
\label{subsec:deadlock_abc}
In order to detect deadlock, we needed a way to determine the holding resources
that different threads are trying to use at the same time. For this, we used two
special pointcuts lock() and unlock(). We then used a deadlock detecting
algorithm, which is an algorithm commonly found in the operating system context
to help us determine if the program is encountering a deadlock.

The pointcut lock() matches a particular point in the program when it is a
synchronized block or a synchronized method. It also determines if a special
Java class, \textit{ReentrantLock}, is being used in the program. We bind the
parameter of the locking code to expose the resource to the advice for futher processing. The
pointcut unlock() matches when the previous resource held by the pointcut lock()
has been released. We needed this information to help us determine deadlock
using the deadlock algorithm (used in most operating systems context).
In the process of detecting the deadlock with the above two mentioned pointcuts
in the processing of multithreading, we have made use of RacerAJ, an extension
of ABC, which includes the above two implemented pointcuts logic.

A deadlock scenario will occur if two or more threads are using
different resources at time\textsubscript{i}, and are trying to use each
other's resources at time\textsubscript{n} when the resource owner has not
release its resource.
A figure is shown in figure~\ref{fig:deadlock} to illustrate the deadlock
scenario.

\begin{figure}
    \centering
    \includegraphics{images/deadlock.jpg}
    \caption{An example of a deadlock scenario where two threads are fighting
    for the same resource}
    \label{fig:deadlock}
\end{figure}

In detecting the deadlock, we use the deadlock algorithm which is commonly found
in the context of Operating System to help us determine which threads are in a
deadlock state.
For every thread that is processing, we would keep track of its identifier and
the resource information that are held by the application. More importantly, we
want to know how much of each resource each process can possibly request, how
much of each process is currently holding and how much of each resource the
system currently has available. Resources may only be allocated to a process if
the request is less than or equals to the maximum resources and the request is
less than or equals to the available resources. If the request has exceeded the
maximum available, then the process has crossed the maximum claim made by
it. If the request has exceeded the available resources, the thread will wait
until resources are available. Having all these information will enable us to
decide if the thread is safe or unsafe, and giving us an estimate to know when
we might encounter a deadlock.

\subsection{Deadlock Algorithm}
In this section, we will display the psedocode of the deadlock algorithm
systematically.

1. We first create 2 placeholders \textit{Work} and \textit{Finish}.
\textit{Work} is used to hold the resources that are available to the system
for the threads to request and \textit{Finish} contains all the threads
available inside the program. We let Work and Finish each be vectors of length
\textit{m} and \textit{n} respectively and initialize them as follow: \\
(a) Work = Available (We imagine \textit{Work} as a warehouse where threads
request resources from it) \\
(b) For \textit{i} = 1,2, \ldots, \textit{n}, if Allocation\textsubscript{i} does
not equals to 0, then Finish[i] = false; Otherwise, Finish[i] = true.

2. We then find an index \textit{i} such that both:\\
(a) Finish[i] == false \\
(b) $Request\textsubscript{i} \le $Work\\
If Finish[i] is false, it means the thread residing in it has not completed
running. \textit{Request} that is less than \textit{work} would indicate that
the resource is still available for grabbing.

If no such \textit{i} exists, we proceed to step 4. This would mean that all
the threads have either finished their execution or that there is no more
available resource for grabbing.

3. Work = Work + Allocation\textsubscript{i} \\
Finish[i] = true \\
go to step 2.\\
When a thread has finished using the resource, it would release it according to
the procedure defined in step 3. The thread would indicate that it has finished
executing by setting its index in the Finish vector to true, and releasing the
resource back to the Work. In this case, Work will increment by 1.

4. If Finish[i] == false, for some i, $1 \le i \le $n, then the system is in a
deadlock state. Moreover, if Finish[i] == false, then thread \textit{i} is
deadlocked.

This algorithm requires an order of O(m x n\textsuperscript{2}) operations to
detect whether the system is in deadlocked state. 

We presented an example of the Deadlock Algorithm described above to better
illustrate the workflow in detecting deadlock.
Suppose there are five different threads t0 through t4, three resources types: 
A (7 instances), B (2 instances), and C (6 instances).

Snapshot at time T\textsubscript{0}:

\begin{table}[h]
\begin{tabular}{lllllllllllll}
                                  &                       & \textbf{A}             & \textbf{B}             & \textbf{C}             &                       & \textbf{A}             & \textbf{B}             & \textbf{C}             &                       & \textbf{A}             & \textbf{B}             & \textbf{C}             \\ \cline{1-1} \cline{3-5} \cline{7-9} \cline{11-13} 
\multicolumn{1}{|l|}{\textbf{t0}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} \\ \cline{1-1} \cline{3-5} \cline{7-9} \cline{11-13} 
\multicolumn{1}{|l|}{\textbf{t1}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  \\ \cline{1-1} \cline{3-5} \cline{7-9} \cline{11-13} 
\multicolumn{1}{|l|}{\textbf{t2}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  \\ \cline{1-1} \cline{3-5} \cline{7-9} \cline{11-13} 
\multicolumn{1}{|l|}{\textbf{t3}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  \\ \cline{1-1} \cline{3-5} \cline{7-9} \cline{11-13} 
\multicolumn{1}{|l|}{\textbf{t4}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  \\ \cline{1-1} \cline{3-5} \cline{7-9} \cline{11-13} 
\end{tabular}
\end{table}

Sequence <t0, t2, t3, t1, t4> will result in Finish[i] = true for all i.

t2 requests an additional instance of type C.

\begin{table}[h]
\begin{tabular}{lllll}
                                  &                       & \multicolumn{3}{l}{\textit{Request}}                                     \\
                                  &                       & \textbf{A}             & \textbf{B}             & \textbf{C}             \\ \cline{1-1} \cline{3-5} 
\multicolumn{1}{|l|}{\textbf{t0}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} \\ \cline{1-1} \cline{3-5} 
\multicolumn{1}{|l|}{\textbf{t1}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{1} \\ \cline{1-1} \cline{3-5} 
\multicolumn{1}{|l|}{\textbf{t2}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{1} \\ \cline{1-1} \cline{3-5} 
\multicolumn{1}{|l|}{\textbf{t3}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{1} \\ \cline{1-1} \cline{3-5} 
\multicolumn{1}{|l|}{\textbf{t4}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{2} \\ \cline{1-1} \cline{3-5} 
\end{tabular}
\end{table}

The states are then that we can reclaim resources held by thread t0, but we have
insuficient resources to fulfill the other thread's requests. Deadlock thus
exists, consisting of the threads: t1, t2, t3, and t4.

After detecting the deadlock in the threads, we will want to recover from it.
There are a few approaches to recover from deadlock: \\
1) inform the user about the deadlock and ask him to take manual intervention,
\\
2) terminate the threadsccthat are in the deadlock, or \\
3) release the resources that are in the deadlock cycle.

We have chosen the first approach in recovering from the
deadlock. We will prompt the user that a deadlock has occurred, with the
necessary information such as the method name and the line number where the
deadlock is detected from this execution of the source code line, and let the
user decide for himself the next course of action that he wants to take.
We have chosen not to terminate the threads automatically as we felt that some of the threads may
be important to the user (i.e. processing volatile data which have not been
serialized) and terminating it may cause the user to lose critical information.
Releasing resources that are in the deadlock may also cause loss of information.
Hence, we have decided that the best approach is to let the user terminate the
thread on his own, based on his own judgement.

\subsection{Implementation of Deadlock Detection}
\label{subsec:implement_deadlock}
In the above section, we have described how this can be achieved. In this
section, we chose some of the important codes that were implemented with Aspects
using the said technique in realising our approach.

In figure~\ref{fig:deadlock_lock}, the pointcut lock is used to capture the
resource object whereas in figure~\ref{fig:deadlock_unlock}, the pointcut lock
is used to release the resource object after the thread has finished using.

\begin{figure}
    \centering
    \includegraphics[scale=0.5]{images/deadlock_lock.pdf}
    \caption{A lock() pointcut used in the actual code implementation to detect
    deadlock.}
    \label{fig:deadlock_lock}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[scale=0.5]{images/deadlock_unlock.pdf}
    \caption{A unlock() pointcut used in the actual code implementation to
    detect deadlock.}
    \label{fig:deadlock_unlock}
\end{figure}

\subsection{Detecting Infinite Loop using ABC}
\label{subsec:infinite_loop_abc}
In detecting for inifinite loop, we have decided to simulate a control call
graph by using the aspect feature of ABC. If a call to a function is being made
repeatedly to a certain number, we will suspect that this is an infinite loop
and allows the user to break the loop.

We make use of the simple logic that the hashcode of every object is unique to
determine the object instance that is making the method call. In this case, if
the object instance is executing the same method repeatedly, we will be able to
suspect that it has encounter an infinite loop. We also make use of the
following pointcut \textit{execution(* *(..))} to allow us to capture every
method joinpoint of the application.

For every execution joinpoint, we will store the object instance's hashcode and
its calling method. In this case, we are able to detect the sequences and if
the common sequence has been repeated multiple times according to our defined
threshold figure, we will decide that this method execution has gone into an
infinite loop. In deciding for the threshold number, we do not want to iimit it
to too low or set to a very high number. By limiting it to a low number, the
chances of detecting a false infinite loop is higher. If we set the number too
high, the program may be wasting resources and time inside the infinite loop.
Therefore, we have chosen 1000 as the threshold figure. We feel that it is just
appropriate in detecting for an infinite loop.

\subsection{Implementation of Infinite Loop Detection}
\label{subsec:implement_loop}
In the above section, we have described how detecting infinite loop can be
achieved.
In this section, we chose some of the important codes that were implemented with Aspects
using the said technique in realising our approach.

In figure~\ref{fig:loop_code}, we can see that the pointcut was defined to
capture and track all the method calls for detecting common repeated patterns as
infinite loop.

\begin{figure}
    \centering
    \includegraphics[scale=0.5]{images/loop_code.pdf}
    \caption{A lock() pointcut used in the actual code implementation to detect
    deadlock.}
    \label{fig:loop_code}
\end{figure}

